package com.zp.self.module.level_4_算法练习.数学.数学推理;
import org.junit.Test;

/**
 * @author By ZengPeng
 */
public class 力扣_1071_字符串的最大公因子 {
    @Test
    public void main() {
        
        Solution solution = new 力扣_1071_字符串的最大公因子().new Solution();
        System.out.println(solution);
    }

    /**
     题目：对于字符串 s 和 t，只有在 s = t + ... + t（t 自身连接 1 次或多次）时，我们才认定 “t 能除尽 s”。
     给定两个字符串 str1 和 str2 。返回 最长字符串 x，要求满足 x 能除尽 str1 且 X 能除尽 str2 。

     示例 1：
         输入：str1 = "ABCABC", str2 = "ABC"
         输出："ABC"

         示例 2：
         输入：str1 = "ABABAB", str2 = "ABAB"
         输出："AB"

         示例 3：
         输入：str1 = "LEET", str2 = "CODE"
         输出：""

     分析：【RB 💖💖💖💖】
        大神：所以如果 str1 + str2 === str2 + str1 就意味着有解。
             我们也很容易想到 str1 + str2 !== str2 + str1 也是无解的充要条件。
             当确定有解的情况下，最优解是长度为 gcd(str1.length, str2.length) 的字符串。
                    --执行耗时:1 ms,击败了68.22% 的Java用户
                    --编码耗时:[超过20分钟]


     边界值 & 注意点：
        1.
     **/
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public String gcdOfStrings(String str1, String str2) {
        if(!(str1+str2).equals(str2+str1)) return "";
        return str1.substring(0,gcd(str1.length(), str2.length()));
    }
    //求最大公约数，这太强了
    public int gcd(int x, int y) {
            return x == 0 ? y : gcd(y % x, x);
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}